//对链表进行插入排序

package Leetcode;

public class Solution147 {

    public ListNode insertionSortList(ListNode head) {
        int length = 0; // 链表长度
        int sortLength = 0; // 已经排好的最后一个元素的下标
        ListNode node = head;
        // 获取链表长度
        while (node != null) {
            node = node.next;
            length++;
        }
        // 插入排序
        for (int i = 0; i < length - 1; i++) { // 排序的次数
            // 找到待排节点的上一个节点
            node = head;
            for (int j = 0; j < sortLength; j++) {
                node = node.next;
            }
            // 获取待排节点
            ListNode insert = node.next;
            // 把待排节点从链表删除
            node.next = insert.next;
            // 找到插入位置的上一个节点
            ListNode pre = new ListNode();
            pre.next = head;
            // 需要与每个排好序的节点进行判断，返回最后一个比insert小的节点，即插入的前节点
            for (int j = 0; j <= sortLength; j++) {
                if (insert.val < pre.next.val)
                    break;
                else
                    pre = pre.next;
            }
            // 插入
            // 如果不是头节点
            if (pre.next != head) {
                insert.next = pre.next;
                pre.next = insert;
            } else {
                insert.next = head;
                head = insert;
            }
            sortLength++;
        }
        return head;
    }

}
